package com.monday.divide.and.conquer;

import java.util.Arrays;

/**
 * 逆序对个数
 *
 *   假设我们有 n 个数据，我们期望数据从小到大排列，那完全有序的数据的有序度就是 n(n-1)/2，逆序度等于 0；
 *   相反，倒序排列的数据的有序度就是 0，逆序度是 n(n-1)/2。除了这两种极端情况外，我们通过计算有序对或者逆序对的个数，来表示数据的有序度或逆序度。
 */
public class NumberOfInversePairs {

    /**
     *  求逆序对个数
     *   1、将数组分成前后两部分
     *   2、计算前半部分逆序对个数  k1
     *   3、计算后半部分逆序对个数  k2
     *   4、计算前半部分与后半部分的序对个数  k3
     *   5、最终数组的逆序对个数即： k1 + k2 + k3
     */
    public int numOfInversePairs(int[] nums) {
        System.out.println("原始数据：" + Arrays.toString(nums));

        int result = count(nums, 0, nums.length - 1);

        System.out.println("逆序对个数：" + result);
        System.out.println("计算后数据：" + Arrays.toString(nums));
        System.out.println("==================================>\n");
        return result;
    }

    private int count(int[] nums, int p, int r) {
        if (p >= r) {
            return 0;
        }

        int q = (p + r) / 2;
        int k1 = count(nums, p, q);
        int k2 = count(nums, q + 1, r);
        int k3 = mergeAndCount(nums, p, q, r);

        return  k1 + k2 + k3;
    }


    /**
     *  计算前后两部分之间的逆序对个数
     * @param nums ： 数组
     * @param p ： 前半部分起始下标
     * @param q ： 前半部分结束下标
     * @param r ： 后半部分结束下标
     */

    private int mergeAndCount(int[] nums, int p, int q, int r) {
        int num = 0;
        int[] temp = new int [r - p + 1];
        int tempIndex = 0;

        // 前半部分遍历索引
        int i = p;
        // 后半部分遍历索引
        int j = q + 1;

        while(i <= q && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[tempIndex++] = nums[i++];
            } else {
                temp[tempIndex++] = nums[j++];
                // 计算 p 到 q 区间（即前半部分）比 nums[j] 大的数量
                num += q - i + 1;
            }
        }

        // 前半部分剩余, 无需重复添加个数--上面的循环已经计算过一次
        while( i <= q) {
            temp[tempIndex++] = nums[i++];
        }
        // 后半部分剩余
        while( j <= r) {
            temp[tempIndex++] = nums[j++];
        }

        // 替换原数组值
        for(tempIndex = 0; tempIndex < temp.length; tempIndex++) {
            nums[p + tempIndex] = temp[tempIndex];
        }

        return num;
    }
}
